package com.github.hgkmail.hello.leetcode101.firstsearch;

public class LC200NumberOfIslands {
    //辅函数helper
    public int findArea(char[][] grid, int[][] visited, int i, int j) {
        //边界判定
        if (i<0 || i>=grid.length || j<0 || j>=grid[0].length || visited[i][j]==1) {
            return 0;
        }
        //已访问
        visited[i][j]=1;
        //无效节点
        if (grid[i][j]=='0') {
            return 0;
        }
        //有效节点
        int area=1;
        //把边界判断交给下个递归调用
        area += findArea(grid, visited, i-1, j) + findArea(grid, visited, i+1, j)
                + findArea(grid, visited, i, j-1) + findArea(grid, visited, i, j+1);
        return area;
    }
    //主函数
    public int numIslands(char[][] grid) {
        //base case
        if (grid.length<=0 || grid[0].length<=0) {
            return 0;
        }
        //全局状态变量初始化
        int[][] visited=new int[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                visited[i][j]=0;
            }
        }
        //遍历所有可搜索的位置
        int num=0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (findArea(grid, visited, i, j)>0) {
                    num+=1;
                }
            }
        }
        return num;
    }
    public static void main(String[] args) {

    }
}
